<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
<div>随机生成长度为10000的数组，k设置为5000</div>
<div>
  <div>方法1：<span id="way1">结果：--  时间：--</span></div>
  <div>方法2：<span id="way2">结果：--  时间：--</span></div>
  <div>方法3：<span id="way3">结果：--  时间：--</span></div>
</div>

<button id="btn1">开始执行</button>
<script>
var k = 5000;
document.getElementById('btn1').onclick = function() {
  // const nums = [52, 2, 11, 134, 34, 124, 123, 25, 17, 24, 546, 52, 54, 34, 73, 56, 34, 37, 92, 4, 26, 432, 42, 424, 12, 56743, 536, 245, 34523, 342523, 43534, 54, 454, 35245, 52, 214, 53, 7, 3234, 432, 312]

  var nums = new Array(k);
  for (let i = 0; i < 10000; i++) {
    nums[i] = Math.floor(Math.random() * 10000) 
  }
  var result = '';
  var numsCopy = nums.slice();
  var start = performance.now();
  var end = 0;
  result = findKthLargest1(numsCopy, k);
  end = performance.now();
  document.getElementById('way1').innerHTML = '结果：' + result + ' 时间：' +  (end - start).toFixed(2);

  numsCopy = nums.slice();
  start = performance.now();
  result = findKthLargest2(numsCopy, k);
  end = performance.now();
  document.getElementById('way2').innerHTML = '结果：' + result + ' 时间：' + (end - start).toFixed(2);

  numsCopy = nums.slice();
  start = performance.now();
  result = findKthLargest3(numsCopy, 0, nums.length-1, k)
  end = performance.now();
  document.getElementById('way3').innerHTML = '结果：' + result + ' 时间：' + (end - start).toFixed(2);
}

// api排序，取第k-1个
function findKthLargest1(nums, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  return nums.sort((a, b) => b - a)[k-1]
};

// 暴力循环法（选择排序）
function findKthLargest2(nums, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  let kTh = 0
  for (let i = 0; i < k; i++) {
    let max =nums[i]
    let position = i
    for (let j = i+1; j < nums.length; j++) {
      if(nums[j] > max) {
        max = nums[j];
        position = j;
      } 
    }
    if(i === k-1) kTh = max;
    [nums[i], nums[position]] = [nums[position], nums[i]];
  }
  return kTh
};

// 快速排序变异
function findKthLargest3(nums, left, right, k) {
  if(k >= nums.length || k < 0) throw('k值超出数组长度范围')
  const targetIndex = k -1;
  let partitionIndex = partition(nums, left, right);

  while(partitionIndex !== targetIndex) {
    if(partitionIndex > targetIndex){
      right = partitionIndex - 1
      partitionIndex = partition(nums, left, right)
    } else {
      left = partitionIndex + 1;
      partitionIndex = partition(nums, left, right)
    }
  }
  return nums[partitionIndex]


  function partition(arr, left, right) {
    // 分区操作
    
    // var pivot = Math.floor(Math.random()*(right - left) + left); // 设定基准值（pivot）
    // [arr[pivot], arr[left]] = [arr[left], arr[pivot]];
    var pivot = left
    var index = left + 1;
  
    for (var i = index; i <= right; i++) {
      if (arr[i] > arr[pivot]) {
        [arr[i], arr[index]] = [arr[index], arr[i]];
        index++;
      }
    }
    [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
    return index - 1;
  }
}


</script>
</body>
</html>